Version francaise:

Expressivité et succincté des automates quantitatifs déterministes en histoire

Les automates déterministes en histoire sont un modèle intermédiaire entre le déterminisme et le non-déterminisme, qui profite d'une partie du pouvoir du non-déterminisme sans perdre toutes les propriétés algorithmiques du déterminisme. Ils sont particulièrement utiles pour résoudre des problèmes de synthèse, représentés comme des jeux. L'un de leurs attraits est qu'ils peuvent être plus expressifs et/ou plus succincts que les automates déterministes.

Dans ce projet, l'étudiant étudiera l'expressivité relative et la succincté d'automates déterministes en histoire quantitative, ainsi que le problème de decidabilité du determinisme en histoire.

English version:

Expressiveness and succinctness of quantitative history-deterministic automata

History-deterministic automata are an intermediate model between determinism and nondeterminism, which enjoy some of power of nondeterminsm without losing all of the algorithmic properties of determinism. They are particularly useful for solving synthesis problems, represented as two-player games. One of their appeals is that they can be more expressive and/or more succinct than deterministic automata.

In this project the student will study the relative expressivity and succinctness of quantitative history-deterministic automata, as well as the question of deciding whether an automaton is history-deterministic.

There will be games, algorithms and automata.